1. Field of the Invention
The present invention relates to transposition circuit for transposing matrix data (data packets in the form of matrices) in order, for example, to perform discrete cosine transform or another procedure.
2. Description of Related Art
FIGS. 5(A)–5(C) are diagrams illustrating conventional transposition of matrix data. FIG. 5A is a block diagram depicting the structure of a transposition circuit. FIG. 5B is an image diagram depicting memory content. FIG. 5C is a timing chart depicting the operation of a transposition circuit.
A transposition circuit comprises a random-access memory (hereinafter “RAM”) 10 and an address generator 12, as shown in FIG. 5A. RAM 10 is equipped with an input port and an output port. The address generator 12 generates a write address WA and a read address RA on the basis of a clock signal CK. Input data DI inputted to the input port of RAM 10 is written to the storage area in RAM 10 specified by the write address WA. To read data from RAM 10, the storage area in the RAM 10 where this data is stored is specified by the read address RA. The data thus read is outputted as output data DO from the output port of RAM 10. The address generator 12 can specify the write address WA and the read address RA separately. Consequently, RAM 10 allows data to be read and written independently and concurrently.
Such circuit architecture allows the read sequence of output data DO to be varied in conformity with the write sequence of the input data DI sequentially inputted in matrix format. Output data DO can therefore be converted to a transposed matrix format.
FIG. 5B depicts the storage areas of RAM 10. Numbers in the drawing indicate addresses of storage areas. In this example, data arranged as a 4×4 matrix is processed, so 16 storage areas designated by symbols 0 to 15 are provided to RAM 10.
Transposition of data arranged as a 4×4 matrix will now be described with reference to FIG. 5C.
During periods 0 to 15, the first 16 data d0 to d15 are inputted as input data DI to RAM 10 according the aforementioned sequence in sync with clock signals CK. The address generator 12 outputs write addresses WA 0 to 15 for the corresponding data d0 to d15. Data d0 to d15 are thereby stored to the corresponding addresses 0 to 15 of RAM 10.
During period 16, the address generator 12 generates address 0 as a read address RA. In accordance with this, data d0 stored at address 0 of RAM 10 is outputted as output data DO. During period 16, the address generator 12 also outputs address 0 as a write address WA. In accordance with this, data d16 provided as input data DI is stored to address 0 of RAM 10.
During period 17, the address generator 12 outputs address 4 as a read address RA. In accordance with this, data d4 stored at address 4 of RAM 10 is outputted as output data DO. During period 17, the address generator 12 also outputs address 4 as a write address WA. In accordance with this, data d17 provided as input data DI is stored to address 4 of RAM 10.
Similarly, during periods 18, 19, 20, 21, . . . the address generator 12 outputs addresses 8, 12, 1, 5, . . . as read addresses RA. In accordance with this, data d8, d12, d1, d5, . . . stored at addresses 8, 12, 1, 5, . . . of RAM 10 are outputted as output data DO. In these periods 18, 19, 20, 21, . . . the address generator 12 also outputs addresses 8, 12, 1, 5, . . . as write addresses WA. In accordance with this, data d18, d19, d20, d21, . . . provided as input data DI are stored to addresses 8, 12, 1, 5, . . . of RAM 10.
Thus, data d0, d1, d2, and d3 corresponding to the components in the first row of the matrix are first written to RAM 10 in the order indicated. Data d4, d5, d6, and d7 corresponding to the components in the second row of the matrix are then written to RAM 10 in the order indicated. Data d8, d9, d10, and d11 corresponding to the components in the third row of the matrix are subsequently written to RAM 10 in the order indicated. Data d12, d13, d14, and d15 corresponding to the components in the fourth row of the matrix are written after that to RAM 10 in the order indicated.
Data d0, d4, d8, and d12 corresponding to the components in the first column of the matrix are read from RAM 10 in the order indicated. Data d1, d5, d9, and d13 corresponding to the components in the second column of the matrix are subsequently read from RAM 10 in the order indicated. Data d2, d6, d10, and d14 corresponding to the components in the third column of the matrix are then read from RAM 10 in the order indicated. Data d3, d7, d11, and d15 corresponding to the components in the fourth column of the matrix are read after that from RAM 10 in the order indicated.
Matrix data inputted to the transposition circuit is thus converted to data arranged as a matrix obtained by interchanging the rows and columns of the original matrix.
Conventional transposition circuits, however, are configured such that a single data packet is read or written per period. A processing time of 2N2 periods will therefore be needed to process data arranged as an N×N matrix (where N is an integer of 2 or greater). A resulting disadvantage is that the processing time increases dramatically with increased matrix size.